package com.ting.test.algorithms.大厂刷题班;

/**
 * 返回一个二维数组中，子矩阵的最大累加和是多少
 * 思路
 * 遍历所有的可能的子矩阵
 * 找出所有以I行开头,j行结尾的子矩阵的最大累加和
 * <p>
 * 任意一个以I行开头,j行结尾的子矩阵，都可以通过空间压缩，变成一个一维数组，这样就可以利用求数组中的最大累加和的问题思路
 */
public class 矩阵中中子矩阵的最大累加和 {
    public static void main(String[] args) {
        int[][] arr = new int[1][2];
        int sum = process(arr);
    }

    private static int process(int[][] arr) {
        if (arr == null) {
            return 0;
        }


        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            int[] tempArr = arr[i];
            for (int j = i; j < arr.length; j++) {
                if (j != i) {
                    tempArr = gen(tempArr, arr[i]);
                }
                int current = getMaxSubSum(tempArr);
                max = Math.max(max, current);
            }

        }
        return max;
    }

    private static int getMaxSubSum(int[] tempArr) {
        if (null == tempArr) {
            return 0;
        }

        int pre = tempArr[0];
        int max = pre;
        for (int i = 0; i < tempArr.length; i++) {
            max = Math.max(Math.max(pre, pre + tempArr[i]), tempArr[i]);
            pre = max;
        }
        return max;

    }

    private static int[] gen(int[] tempArr, int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            tempArr[i] = tempArr[i] + arr[i];
        }
        return new int[0];
    }
}
